package _7_斐波那契数列;
/**
 * 题目描述
 * 大家都知道斐波那契数列，现在要求输入一个整数n，
 * 请你输出斐波那契数列的第n项（从0开始，第0项为0）。
 * n<=39
 */
public class Solution {
    public int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        //int dp[]  = new int[n+1];
        int prepre=1;
        int pre=1;
        int current=0;
        for(int i=3;i<=n;i++){
            current = prepre+pre;
            prepre = pre;
            pre = current;
        }
        return current;
    }
}
